'''
https://leetcode.cn/problems/maximum-number-of-events-that-can-be-attended/
'''
import heapq
from typing import List


class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        n = len(events)
        events.sort()
        min_day = events[0][0]
        max_day = max(event[1] for event in events)

        q = []
        i = 0
        ans = 0
        for t in range(min_day, max_day + 1):
            while q and q[0] < t:
                heapq.heappop(q)
            while i < n and events[i][0] == t:
                heapq.heappush(q, events[i][1])
                i += 1
            if q:
                heapq.heappop(q)
                ans += 1
        return ans


# events = [[1,2],[2,3],[3,4]]
# events = [[1, 5], [1, 5], [1, 5], [2, 3], [2, 3]]
events = [[27,27],[8,10],[9,11],[20,21],[25,29],[17,20],[12,12],[12,12],[10,14],[7,7],[6,10],[7,7],[4,8],[30,31],[23,25],[4,6],[17,17],[13,14],[6,9],[13,14]]
print(Solution().maxEvents(events))
